package ListThreadedBinaryTree;

/**
 * 实现中序遍历线索化二叉树：结果正好是从小到大的顺序
 */
public class ListThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        Person root = new Person(1,"tom");
        Person node1 = new Person(3,"jack");
        Person node2 = new Person(6,"luyi");
        Person node3 = new Person(8,"mary");
        Person node4 = new Person(10,"ll");
        Person node5 = new Person(14,"dim");

        //创建二叉树
        root.setLeft(node1);
        root.setRight(node2);
        node1.setLeft(node3);
        node1.setRight(node4);
        node2.setLeft(node5);

        // 测试线索化
        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setRoot(root);
        threadedBinaryTree.threadedNodes();

        // 以node4 10号 节点做测试
        Person leftNode = node4.getLeft();
        Person rightNode = node4.getRight();
        // 没有线索化之前 leftNode = rightNode = null;
        System.out.println("10号节点的前驱节点为 "+leftNode);// 10号节点的前驱节点为 HeroNode1{no=3, name='jack'}
        System.out.println("10号节点的后继节点为 "+rightNode);// 10号节点的后继节点为 HeroNode1{no=1, name='tom'}

        //调用遍历线索化二叉树的方法
        threadedBinaryTree.listThreadedBinaryTree();

    }
}

//创建二叉树，二叉树中也需要具备前中后排序方法:实现了线索化功能的二叉树
class ThreadedBinaryTree {
    //创建一个根节点，必须被初始化，可以是在构造方法中初始化
    private Person root;
    // 为了实现线索化 需要创建一个指向当前节点的前驱节点的指针
    // pre在递归进行线索化时 总是指向前一个节点
    private Person pre = null;

    public ThreadedBinaryTree() {
    }

    public ThreadedBinaryTree(Person root) {
        this.root = root;
    }

    public Person getRoot() {
        return root;
    }

    public void setRoot(Person root) {
        this.root = root;
    }

    //遍历线索化二叉树方法:中序遍历输出，跟中序线索化有关系
    // 二叉树是被什么顺序线索化的，就必须按照什么顺序遍历线索化输出。
    public void listThreadedBinaryTree(){
        //创建辅助指针
        Person temp = root;
        while (temp != null){
            //找到最左边的线索化节点
            while (temp.getLeftType() != 1){
                temp = temp.getLeft();
            }
            //输出当前节点
            System.out.println(temp);
            while (temp.getRightType() == 1){
                //若当前线索化的节点后一个节点是子节点，不是子树，则直接输出
                temp = temp.getRight();
                System.out.println(temp);
            }
            //若当前线索化的节点后一个节点是子树,则不能直接输出，而是先遍历输出它的左子节点，再输出其他，所以得后移一位指针
            temp = temp.getRight();
        }
    }

    //重载对二叉树进行 “中序线索化” 的方法
    public void threadedNodes(){
        this.threadedNodes(root);
    }
    /**
     *     编写对二叉树进行 “中序线索化” 的方法
     * @param node:当前需要线索化的节点，一般为根节点
     */
    public void threadedNodes(Person node){
        //1.若node为空，则不能线索化
        if (node == null) {
            System.out.println("节点为空，不能进行线索化！");
            return;
        }
        //（一）先线索化左子树
        if (node.getLeft() != null) {
            this.threadedNodes(node.getLeft());
        }
        //（二）再线索化当前节点
        if (node.getLeft() == null) {
            //当前节点必须是叶子节点，若为当前节点的左节点空，则将前一个节点赋给当前节点的左节点
            node.setLeft(pre);
            //只要是线索化，那么都是指向后继节点，不可能是子树，只有一开始构建二叉树的时候，才会形成子节点指向子树节点
            node.setLeftType(1);
        }
        if (pre != null && pre.getRight() == null) {
            //当前节点必须是叶子节点，若为当前节点的右节点空，则将前一个节点赋给当前节点的右节点
            pre.setRight(node);
            pre.setRightType(1);
        }
        // 很重要 每次处理完当前节点后  让这个节点变成下一个节点的前驱节点
        pre = node;
        //（三）再线索化右子树
        if (node.getRight() != null) {
            this.threadedNodes(node.getRight());
        }
    }

    //创建前序遍历方法，打印整个二叉树的方法
    public void preOrder() {
        if (root != null) {
            root.preOrder();
        } else {
            System.out.println("二叉树为空，没有数据可以遍历输出！");
        }
    }

    //创建中序遍历方法，打印整个二叉树的方法
    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("二叉树为空，没有数据可以遍历输出！");
        }
    }

    //创建后序遍历方法，打印整个二叉树的方法
    public void postOrder() {
        if (root != null) {
            root.postOrder();
        } else {
            System.out.println("二叉树为空，没有数据可以遍历输出！");
        }
    }

    //创建前序查找算法:根据用户id查找
    public Person preOrderSearch(int id){
        if (root != null) {
            return root.preOrderSearch(id);
        }else {
            return null;
        }
    }

    //创建中序查找算法:根据用户id查找
    public Person infixOrderSearch(int id){
        if (root != null) {
            return root.infixOrderSearch(id);
        }else {
            return null;
        }
    }

    //创建后序查找算法:根据用户id查找
    public Person postOrderSearch(int id){
        if (root != null) {
            return root.postOrderSearch(id);
        }else {
            return null;
        }
    }

    //创建删除节点的方法
    // 递归删除节点的要求：
    // 1 如果删除的节点是叶子节点 ,则删除该节点
    // 2 如果是非叶子节点 则删除该子树
    // 3 需要找到待删除节点的上一个节点，进行判断，因为二叉树是单向的，所以不能直接找当前节点进行判断
    public void delNode(int id){
        if (root != null) {
            if (root.getId() == id) {//删除的是根节点，直接判断返回
                root = null;
                return;
            }
            root.delNode(id);
        }else {
            System.out.println("根节点为空，没有数据可以删除！");
        }
    }

}

//创建添加到二叉树的节点元素，必须具备前中后三序排序方法
class Person {
    private int id;
    private String name;
    private Person left;     //默认null
    private Person right;    //默认null
    // 说明
    // leftType = 0 表示指向左子树 leftType = 1 表示指向前驱节点
    // rightType = 0 表示指向右子树 rightType = 1 表示指向后继节点
    private int leftType;
    private int rightType;

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public Person() {
    }

    public Person(int id, String name) {
        this.id = id;
        this.name = name;
    }

    //创建前序遍历方法
    public void preOrder() {
        //1.先输出根节点
        System.out.println(this);
        //2.若存在左子节点，则再递归遍历左子节点
        if (this.left != null) {
            this.left.preOrder();
        }
        //3.若存在右子节点，则再递归遍历右子节点
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    //创建中序遍历方法
    public void infixOrder() {
        //1.若存在左子节点，则先递归遍历左子节点
        if (this.left != null) {
            this.left.infixOrder();
        }
        //2.先输出根节点
        System.out.println(this);
        //3.若存在右子节点，则再递归遍历右子节点
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    //创建后序遍历方法
    public void postOrder() {
        //1.若存在左子节点，则先递归遍历左子节点
        if (this.left != null) {
            this.left.postOrder();
        }
        //2.若存在右子节点，则再递归遍历右子节点
        if (this.right != null) {
            this.right.postOrder();
        }
        //3.先输出根节点
        System.out.println(this);
    }

    //创建前序查找算法：根据用户id
    public Person preOrderSearch(int id){
        //创建一个变量接收找到的结果
        Person res = null;//初始为空

        //1.先判断当前节点的id值，是否与查找值相等
        if (this.id == id) {
            //若相等直接返回当前对象
            return res = this;
        }

        //2.若存在左子节点，则再递归遍历左子节点的 id 值
        if (this.left != null) {
            res = this.left.preOrderSearch(id);
        }
        //判断左子节点有没有找到这个值，若找到直接返回，若没有找到则继续递归遍历右子节点
        if (res != null) {
            return res;
        }

        //3.若存在右子节点，则再递归遍历右子节点
        if (this.right != null) {
            res = this.right.preOrderSearch(id);
        }
        //无论最后一次递归查找有没有结果，都直接返回结果
        return res;

    }

    //创建中序查找算法：根据用户id
    public Person infixOrderSearch(int id) {
        //创建一个变量接收找到的结果
        Person res = null;//初始为空

        //1.若存在左子节点，则再递归遍历左子节点的 id 值
        if (this.left != null) {
            res = this.left.infixOrderSearch(id);
        }
        //判断左子节点有没有找到这个值，若找到直接返回，若没有找到则继续递归遍历右子节点
        if (res != null) {
            return res;
        }

        //2.先判断当前节点的id值，是否与查找值相等
        if (this.id == id) {
            //若相等直接返回当前对象
            return res = this;
        }

        //3.若存在右子节点，则再递归遍历右子节点
        if (this.right != null) {
            res = this.right.infixOrderSearch(id);
        }
        //无论最后一次递归查找有没有结果，都直接返回结果
        return res;
    }

    //创建后序查找算法：根据用户id
    public Person postOrderSearch(int id) {
        //创建一个变量接收找到的结果
        Person res = null;//初始为空

        //1.若存在左子节点，则再递归遍历左子节点的 id 值
        if (this.left != null) {
            res = this.left.infixOrderSearch(id);
        }
        //判断左子节点有没有找到这个值，若找到直接返回，若没有找到则继续递归遍历右子节点
        if (res != null) {
            return res;
        }

        //2.若存在右子节点，则再递归遍历右子节点
        if (this.right != null) {
            res = this.right.infixOrderSearch(id);
        }
        //判断右子节点有没有找到这个值，若找到直接返回，若没有找到则继续递归遍历右子节点
        if (res != null) {
            return res;
        }

        //3.先判断当前节点的id值，是否与查找值相等
        if (this.id == id) {
            //若相等直接返回当前对象
            res = this;
        }

        //无论最后一次递归查找有没有结果，都直接返回结果
        return res;
    }

    //创建删除子节点的方法
    // 递归删除节点的要求：
    // 1 如果删除的节点是叶子节点 ,则删除该节点
    // 2 如果是非叶子节点 则删除该子树
    // 3 需要找到待删除节点的上一个节点，进行判断，因为二叉树是单向的，所以不能直接找当前节点进行判断
    public void delNode(int id){
        //从根节点开始
        //1.先判断左子节点是否是被删除数
        if (this.left != null && this.left.id == id) {
            this.left = null;//将左子节点置空，就是删除左子节点
            return;//结束该方法
        }
        //2.再判断右子节点是否是被删除数
        if (this.right != null && this.right.id == id) {
            this.right = null;//将右子节点置空，就是删除左子节点
            return;
        }
        //3.根节点的左右子节点都不是被删除数，则先向左递归删除
        if (this.left != null) {//若节点下面还有子节点
            this.left.delNode(id);
        }
        //4.根节点的所有左子节点都不是被删除数，则再向右递归删除
        if (this.right != null) {
            this.right.delNode(id);
        }
    }
    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Person getLeft() {
        return left;
    }

    public void setLeft(Person left) {
        this.left = left;
    }

    public Person getRight() {
        return right;
    }

    public void setRight(Person right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "Person{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

}